/**
 * Created by Administrator on 2019/5/17/017.
 */
import SMAP_ListNode from "./SMAP_ListNode.js"

class SMAP_LinkedList {
  constructor() {
    // 初始化为空的开始和结束节点
    this.start = new SMAP_ListNode()
    this.end = new SMAP_ListNode()

    // 初始化开始节点的指向
    this.start.next = this.end
    this.start.prev = null

    // 初始化结束节点的初始化
    this.end.prev = this.start
    this.end.next = null

    // 初始化计数器
    this._idCounter = 0
    this._numNodes = 0
  }

  /**
   *   在双向链表的一个节点前插入另一个节点
   *   @param {SMAP_ListNode} toInsertBefore : 要被插入的节点
   *   @param {object} data : 插入节点的数据
   */
  insertBefore(toInsertBefore, data) {
    const newNode = new SMAP_ListNode(this._idCounter, data)

    newNode.next = toInsertBefore
    newNode.prev = toInsertBefore.prev

    toInsertBefore.prev.next = newNode
    toInsertBefore.prev = newNode

    ++this._idCounter
    ++this._numNodes
  }

  /**
   *   在双向链表的最后一个节点前插入另一个节点
   *   @param {object} data : 插入节点的数据
   */
  addLast(data) {
    this.insertBefore(this.end, data)
  }

  /**
   *   addLast的别名，效果一样
   *   @param {object} data: 插入节点的数据
   */
  add(data) {
    this.addLast(data)
  }

  /**
   *   返回第一个不为空的节点，或者为null
   *   @return {Node/null}
   */
  getFirst() {
    if (this._numNodes === 0) {
      return null
    } else {
      return this.start.next
    }
  }

  /**
   *   返回最后一个不为空的节点，或者为null
   *   @return {SMAP_ListNode/null}
   */
  getLast() {
    if (this._numNodes === 0) {
      return null
    } else {
      return this.end.prev
    }
  }

  /**
   *   返回链表中有效节点的个数
   *   @return {number}
   */
  size() {
    return this._numNodes
  }

  /**
   *   (内部函数) 在链表中获取并返回特定索引位置的节点变量
   *   Use get instead of this function
   *   @param {number} index
   */
  getFromFirst(index) {
    let count = 0
    let temp = this.start.next

    if (index >= 0) {
      while (count < index && temp !== null) {
        temp = temp.next
        ++count
      }
    } else {
      temp = null
    }

    if (temp === null) {
      throw new Error("Index out of bounds.")
    }

    return temp
  }

  /**
   *   在链表中获取并返回特定索引位置的节点变量
   *   @param {number} index
   */
  get(index) {
    let temp = null

    if (index === 0) {
      temp = this.getFirst()
    } else if (index === this._numNodes - 1) {
      temp = this.getLast()
    } else {
      temp = this.getFromFirst(index)
    }

    return temp
  }

  /**
   *   通过调整该节点前后节点的指针指向，从链表中移除该节点，并返回该节点
   *   @param {Node} node
   *   @return {Node}
   */
  remove(node) {
    node.prev.next = node.next
    node.next.prev = node.prev

    --this._numNodes

    return node
  }

  /**
   *   在链表中移除第一个非空的节点并返回，如果链表为空则返回null
   *   @return {Node/null}
   */
  removeFirst() {
    let temp = null

    if (this._numNodes > 0) {
      temp = this.remove(this.start.next)
    }

    return temp
  }

  /**
   *   在链表中移除最后一个非空的节点并返回，如果链表为空则返回null
   *   @return {Node/null}
   */
  removeLast() {
    let temp = null

    if (this._numNodes > 0) {
      temp = this.remove(this.end.prev)
    }

    return temp
  }

  /**
   *   移除链表中的所有节点
   */
  removeAll() {
    this.start.next = this.end
    this.end.prev = this.start
    this._numNodes = 0
    this._idCounter = 0
  }

  /**
   *  输入函数参数，迭代链表中的每一项作为该函数的参数
   *  @param {function} fn
   */
  each(iterator) {
    let temp = this.start

    while (temp.hasNext()) {
      temp = temp.next
      iterator(temp)
    }
  }

  /**
   *  输入函数参数，迭代查找链表中的每一项满足特定的条件（找到即返回）
   *  @param {function} fn
   */
  find(iterator) {
    let temp = this.start
    let found = false
    let result = null

    while (temp.hasNext() && !found) {
      temp = temp.next
      if (iterator(temp)) {
        result = temp
        found = true
      }
    }

    return result
  }

  /**
   *  输入函数参数，迭代查找链表中的每一项满足特定的条件（找到所有才返回）
   *  @param {function} fn
   */
  map(iterator) {
    let temp = this.start
    const results = []

    while (temp.hasNext()) {
      temp = temp.next
      if (iterator(temp)) {
        results.push(temp)
      }
    }

    return results
  }

  /**
   *  addLast的别名，一样的效果
   *  @param {object} data
   */
  push(data) {
    this.addLast(data)
  }

  /**
   *  添加一个节点，并将该节点作为第一个有效节点
   *  @param {object} data
   */
  unshift(data) {
    if (this._numNodes > 0) {
      this.insertBefore(this.start.next, data)
    } else {
      this.insertBefore(this.end, data)
    }
  }

  /**
   *  removeLast的别名
   */
  pop() {
    return this.removeLast()
  }

  /**
   *  removeFirst的别名
   */
  shift() {
    return this.removeFirst()
  }
}

export default SMAP_LinkedList
